In a network system, network forwarding devices such as routers are used to connect a plurality of subnets. A router checks the destination address of a packet received from a subnet to which the router is connected, determines the next hop, and forwards the received packet to the subnet to which the next-hop router or the host is connected. FIG. 1 shows the configuration of a general network system composed of a plurality of subnets connected by routers.
In FIG. 1, R1 and R2 are routers, SN1 is a sub network connected to port P11 of router R1, SN2 is a sub network connected to port P12 of router R1 and port 21 of router R2, H10 and H11 are hosts connected to subnet SN1, H20 and H21 are hosts connected to subnet SN2, and H30 and H31 are hosts connected to subnet SN3.
When a packet is sent from host H10 to host H21, router R1 checks the destination address DA stored in the packet as the header information to find that destination host H21 is on subnet SN2 and that subnet SN2 is connected directly to router R1. Then, router R1 outputs the packet to port P12 which connects to subnet SN2. When outputting the packet, router R1 sets the destination host (H21) as the address to which the packet to is be forwarded next (next hop address).
When a packet is sent from host H10 to host H31, router R1 checks the destination address DA stored in the packet as the header information to find that destination host H31 is on subnet SN3 and that subnet SN3 is connected not directly to router R1 but via router R2. Router R1 outputs the packet to port P21 connected to subnet SN2 to which router R2 is connected. When outputting the packet, router R1 sets router R2 as the address to which the packet to is be forwarded next (next hop address). Upon receiving the packet, router R2, like router R1, checks the destination address DA and forwards the packet to host H31.
Next, referring to FIG. 2, the following describes the search specification used by a router, which has received a packet, to search for the address to which the packet is to be forwarded next and the port to which the packet is to be output. TBL, a path search table, contains configuration definition information entered manually and information acquired through communication of connection information between routers.
With the set of a sub-network address and a sub-network mask length as the search key, the path search table TBL is used to search for an output port, next hop address, and information indicating whether or not the sub-network is connected directly (hereafter called next hop information).
In the path search specification, the mask beginning with the most significant bit and extending for the number of bits indicated by the sub-network mask length is multiplied by the destination address for comparison with a sub-network address. As a result of comparison, multiple entries E1, E2, and E4 with different mask lengths match. Out of the matching entries, the next hop information (next hop 2) of E2 with the longest mask is selected as the search result.
The Radish algorithm is known as one of the quick search methods in accordance with this search specification. The Radish algorithm is described, for example, in “Let's read kernel (8) Path control mechanism at IP layer (2)” by Hide Yamaguchi, pp. 20-25 in UNIX MAGAZINE, April, 1997.
The following describes the Radish algorithm. The Radish algorithm maps the nodes of a tree structure composed of multiple pointer-connected nodes, each having the left and right pointers, to the path entries. When this tree is followed, the left or right pointer of each node is selected to move to the next node until the node to which the desired path entry is mapped is reached.
First, referring to FIG. 3, the tree structure will be described. Because the concept of the tree structure does not depend on the number of bits, the address is three bits in length in FIG. 3 for easy understanding.
As shown in FIG. 3, the nodes are called, beginning with the top of the tree, 0-bit mask node, 1-bit mask nodes, 2-bit mask nodes, and 3-bit mask nodes.
In the 0-bit mask node N0000, one of the left and right pointers is selected according to whether bit 0 of the destination address is 0 or 1 to move down to 1-bit mask node N0001 or N1001. In a 1-bit mask node, one of the left and right pointers is selected according to whether bit 1 is 0 or 1 to move down to 2-bit mask node N0002, N0102, N1002, or N1102. In a 2-bit mask node, one of the left and right pointers is selected according to whether bit 2 is 0 or 1 to move down to 3-bit mask node N0003, N0013, N0103, N0113, N1003, N1013, N1103, or N1113.
When searching for a desired destination address through pointers, beginning at 0-bit mask node N000 of the tree, according to whether the bit is 0 or 1, the 0-bit mask node is always selected. 1-bit mask node N0001 or N1001 is selected, beginning with the left end, when the bits of the destination address is 0XX or 1XX, respectively. 2-bit mask node N0002, N0102, N1002, or N1102 is selected, beginning with the left end, when the bits of the destination address is 00X, 01X, 10X, or 11X, respectively. 3-bit mask node N0003, N0013, N0103, N0113, N1003, N1013, N1103, or N1113 is selected, beginning with the left end, when the bits of the destination address is 000, 001, 010, 011, 100, 101, 110, or 111, respectively. X indicates a ‘don't care’ bit, that is, any bit value, 0 or 1, is acceptable.
Therefore, 0-bit mask node N0000 is selected when the destination address belongs to the sub-network address 000/0. 1-bit mask node N0001 or N1001 is selected when the destination address belongs to the sub-network address 000/1 or 100/1. 2-bit mask node N0002, N0102, N1002, or N1102 is selected when the destination address belongs to the sub-network address 000/2, 010/2, 100/2, or 110/2. 3-bit mask node N0003, N0013, N0103, N0113, N1003, N1013, N1103, or N1113 is selected when the destination address belongs to the sub-network address 000/3, 001/3, . . . or 111/3. The notation “sss/m” indicates that “sss” represents a sub-network address and m represents the mask length.
As described above, the nodes of this tree correspond, one to one, with all subnets each with a unique sub-network address and a mask length.
Nodes N0000, N0013, N0102, N1001, and N1103, which correspond to the entries of the path table shown in FIG. 4, are attached “*” in the tree. When the destination address DA011 is searched for in this tree by checking the pointers if each bit is 0 or 1, it is found that nodes N0000 and N0102, which have “*” attached, correspond to the matching entries. When there are a plurality of path table entries that match the destination address, the rule is that the longest mask-length sub-network is selected. That is, out of matching nodes N0000 and N0102 to which “*” is attached, the path information allocated to node N0102 nearest to the end point is selected as the search result of the path table.
As shown in the search method described above, those nodes to which “*” is not attached and which are not intermediate paths to a node with “*” attached, that is, N0003, N0103, N0113, N1003, N1013, N1113, and N1002, do not affect the search result if removed from the tree. Rather, when “*” is not attached to the bottom-level node, the search becomes more efficient because the search ends before reaching the bottom level. FIG. 5 shows a tree created by removing nodes to which “*” is not attached and which are not intermediate path to a node to which “*” is attached.
FIG. 7 shows a 2-branch (binary) tree which corresponds to the 32-bit address path table shown in FIG. 6 and which is created by the method described above. As shown in the figure, a long string NS1 of nodes with neither a branch nor a “*” is created. The following describes the quick search method in which only one of left and right pointers of a node connects to the next node and the nodes to which path entries are not mapped are removed.
In this quick search method, node string NS1 with no branch or “*” is removed and the immediate higher-level node N000000000 of the removed node string NS1 is connected to the immediate lower-level node N8504000015 in the branch direction (right side in FIG. 7). The resulting tree is shown in FIG. 8. Removing the intermediate nodes like this is called the reduction of a tree.
Next, the path search method for a reduced tree will be described.
In the example shown in FIG. 8, immediately after bit 0 of the 0-bit mask node N000000000 is checked, 15-bit mask node N8504000015 is checked. Therefore, even if bit 15 of 15-bit mask node N850400015 is checked, the intermediate bits, bit 1 to bit 14, cannot be checked. To check bits 1 to 15 in one search operation, bits 1 to 15 of the destination address are compared with bits 1 to 15 of the sub-network address 0x85.04.00.00 of node N8504000015. An equal comparison indicates that the intended node is reached, that is, the node would be reached also by comparing them, one bit at a time, in a non-reduced tree. An unequal comparison indicates that a non-intended node is reached, that is, there would be no destination in the non-reduced tree.
In FIG. 8, an equal condition always occurs in bit 0 because the branch is already selected based on the equality. In general, if a check is made each time a node is reached to see if the correct node is reached, it is guaranteed that the destination address equals the sub-network address of the node for the mask length beginning with bit 0. Thus, when the next node is reached, whether the correct node is reached is checked by comparing the destination address with the sub-network address for the mask length beginning with bit 0 regardless of how many bits were tested before.